package Offer367;

/**
 * 有效的完全平方数
 * 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 * @author 23737
 * @time 2021.11.04
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().isPerfectSquare(14));
        System.out.println(new Solution().isPerfectSquare2(36));
    }
}

class Solution {
    /**
     * 基础版，使用库内置函数
     * @param num
     * @return
     */
    public boolean isPerfectSquare(int num) {
        if (num == 0) return true;
        if (Math.pow((int)Math.sqrt(num),2) == num) return true;
        return false;
    }

    /**
     * 进阶版——不适用任何库函数
     * 二分查找yyds
     * @param num
     * @return
     */
    public boolean isPerfectSquare2(int num) {
        int left = 1;
        int right = num;
        while(left <= right){
            int mid = left+(right-left)/2;
            int temp = num/mid;
            if(temp == mid){
                if((num % mid) == 0) return true;
                left = mid+1;
            }else if(temp < mid){
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return false;
    }
}
